///////////////////////////////////////////////////

template <uint NUM_DWORDS>
TLongBitSet<NUM_DWORDS>::TLongBitSet( const TLongBitSet& src )
{
	for (int i = 0; i < NUM_DWORDS; ++i)
	{
		m_Bits[i] = src.m_Bits[i];
	}
}

template <uint NUM_DWORDS>
inline bool TLongBitSet<NUM_DWORDS>::contains(u32 bitNo) const
{
	ASSERT(bitNo < size());
	u32 ord = bitNo >> 5;
	int f = 1 << (bitNo - (ord << 5));
	return (m_Bits[ord] & f) != 0;
}

template <uint NUM_DWORDS>
inline void TLongBitSet<NUM_DWORDS>::set(u32 bitNo, bool flag)
{ 
	ASSERT(bitNo < size());
	u32 ord = bitNo >> 5; // bitNo / 32
	int f = 1 << (bitNo - (ord << 5)); // 1 << (bitNo % 32)
	m_Bits[ord] = flag ? (m_Bits[ord] | f) : (m_Bits[ord] & ~f);
}

template <uint NUM_DWORDS>
bool TLongBitSet<NUM_DWORDS>::isEmpty()
{
	for (int i = 0; i < NUM_DWORDS; ++i)
	{
		if (m_Bits[i] != 0)
			return false;
	}

	return true;
}

template <uint NUM_DWORDS>
TLongBitSet<NUM_DWORDS> TLongBitSet<NUM_DWORDS>::operator^(const TLongBitSet& src) const
{
	TLongBitSet<NUM_DWORDS> out;
	for (uint i = 0; i < NUM_DWORDS; ++i)
		out.m_Bits[i] = m_Bits[i] ^ src.m_Bits[i];

	return out;
}

template <uint NUM_DWORDS>
TLongBitSet<NUM_DWORDS> TLongBitSet<NUM_DWORDS>::operator&(const TLongBitSet& src) const
{
	TLongBitSet<NUM_DWORDS> out;
	for (uint i = 0; i < NUM_DWORDS; ++i)
		out.m_Bits[i] = m_Bits[i] & src.m_Bits[i];

	return out;
}

template <uint NUM_DWORDS>
bool TLongBitSet<NUM_DWORDS>::operator!=(const TLongBitSet& src) const
{
	for (uint i = 0; i < NUM_DWORDS; ++i)
	{
		if (src.m_Bits[i] != m_Bits[i])
			return true;
	}

	return false;
}
template <uint NUM_DWORDS>
bool TLongBitSet<NUM_DWORDS>::operator==(const TLongBitSet& src) const
{
	for (uint i = 0; i < NUM_DWORDS; ++i)
	{
		if (src.m_Bits[i] == m_Bits[i])
			return true;
	}

	return false;
}

///////////////////////////////////////////////////

template <class T, class Comparer>
uint TPriorityQueue<T, Comparer>::push(const T& item)
{
	uint p = m_Array.size();
	uint p2;

	m_Array.push_back(item);

	do
	{
		if (p == 0)
			break;

		p2 = (p - 1) / 2;

		if (!less(p, p2))
			break;

		std::swap(m_Array[p], m_Array[p2]);
		p = p2;

	} while (true);

	return p;
}

// gets the *smallest* item and remove it (by less operator)
template <class T, class Comparer>
void TPriorityQueue<T, Comparer>::pop()
{
	T result = m_Array[0];

	uint p = 0;
	uint p1, p2, pn;

	m_Array[0] = m_Array.back();
	m_Array.pop_back();

	do
	{
		pn = p;
		p1 = 2 * p + 1;
		p2 = 2 * p + 2;

		if (m_Array.size() > p1 && less(p1, p)) // left is smaller
			p = p1;
		if (m_Array.size() > p2 && less(p2, p)) // right is smaller
			p = p2;

		if (p == pn)
			break;

		std::swap(m_Array[p], m_Array[pn]);

	} while (true);

	return;
}

///////////////////////////////////////////////////

template <class T>
TTightQueue<T>::TTightQueue(u16 maxSize)
{
	ASSERT(maxSize > 1);
	ASSERT(maxSize < u16(-2));

	m_MaxSize = maxSize;
	m_Array = new T[maxSize];
	clear();
}

template <class T>
TTightQueue<T>::~TTightQueue()
{
	delete[] m_Array;
}

template <class T>
bool TTightQueue<T>::empty()
{
	return m_Size == 0;
}

template <class T>
bool TTightQueue<T>::full()
{
	return size() == m_MaxSize;
}

template <class T>
void TTightQueue<T>::clear()
{
	m_Head = 0;
	m_Tail = 0;
	m_Size = 0;
}

template <class T>
u16 TTightQueue<T>::size()
{
	return m_Size;
}

template <class T>
u16 TTightQueue<T>::max_size()
{
	return m_MaxSize;
}

template <class T>
T& TTightQueue<T>::front()
{
	ASSERT(!empty());

	u16 idx = m_Head;
	++idx;
	return m_Array[idx == m_MaxSize ? 0 : idx];
}

template <class T>
void TTightQueue<T>::push_front(const T& value)
{
	ASSERT(!full());

	if (empty())
	{
		++m_Tail;
		if (m_Tail == m_MaxSize)
			m_Tail = 0;
	}

	++m_Size;

	m_Array[m_Head] = value;

	if (m_Head == 0)
		m_Head = m_MaxSize;
	--m_Head;
}

template <class T>
void TTightQueue<T>::pop_front()
{
	ASSERT(!empty());

	--m_Size;

	++m_Head;
	if (m_Head == m_MaxSize)
		m_Head = 0;

	if (empty())
		m_Tail = m_Head;
}

template <class T>
T& TTightQueue<T>::back()
{
	ASSERT(!empty());

	u16 idx = m_Tail == 0 ? m_MaxSize : m_Tail;
	--idx;
	return m_Array[idx];
}

template <class T>
void TTightQueue<T>::push_back(const T& value)
{
	ASSERT(!full());

	if (empty())
	{
		if (m_Head == 0)
			m_Head = m_MaxSize;
		--m_Head;
	}

	++m_Size;

	m_Array[m_Tail] = value;

	++m_Tail;
	if (m_Tail == m_MaxSize)
		m_Tail = 0;
}

template <class T>
void TTightQueue<T>::pop_back()
{
	ASSERT(!empty());

	--m_Size;

	if (m_Tail == 0)
		m_Tail = m_MaxSize;
	--m_Tail;

	if (empty())
		m_Head = m_Tail;
}

template <class T>
class TTightQueue<T>::iterator : public std::iterator<std::bidirectional_iterator_tag, T>
{
public:
	iterator() { m_Queue = NULL; m_Idx = 0; }
	iterator(TTightQueue<T>* queue, u16 idx) : m_Queue(queue), m_Idx(idx) { }

	iterator& 	operator++ () 			{ ++m_Idx; return *this; }
	iterator 	operator++ (int) 		{ iterator tmp(*this); ++(*this); return tmp; }
	iterator& 	operator-- ()			{ --m_Idx; return *this; }
	iterator	operator-- (int)		{ iterator tmp(*this); --(*this); return tmp; }
	T& 			operator* ()			{ return m_Queue->at(m_Idx); }
	T*			operator-> ()			{ return &m_Queue->at(m_Idx); }

	friend bool	operator == (const iterator& a, const iterator& b)	{ return a.m_Idx == b.m_Idx; }
	friend bool operator != (const iterator& a, const iterator& b)	{ return a.m_Idx != b.m_Idx; }

private:
	TTightQueue<T>* 	m_Queue;
	u16 				m_Idx;
};

template <class T>
typename TTightQueue<T>::iterator TTightQueue<T>::begin()
{
	return iterator(this, 0);
}

template <class T>
typename TTightQueue<T>::iterator TTightQueue<T>::end()
{
	return iterator(this, m_Size);
}

template <class T>
T& TTightQueue<T>::at(u16 index)
{
	ASSERT(index < m_Size);

	u16 idx = u16(m_Head + 1 + index);
	if (idx >= m_MaxSize) idx -= m_MaxSize;

	return m_Array[idx];
}

template <class T>
T& TTightQueue<T>::operator[] (u16 index)
{
	return at(index);
}

///////////////////////////////////////////////////
